/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2023-03-15
 * Time:22:09
 */
class Solution {
    //二分查找
    //左闭右开
    public int search(int[] nums, int target) {
        if(nums.length<=0){
            return -1;
        }
        int left=0;
        int right= nums.length;
        while(left<right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid;
            }else if(nums[mid]<target){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    //左闭右闭
    public int search2(int[] nums, int target) {
        int left=0;
        int right= nums.length-1;
        while(left<=right){
            int mid=left+(right-left)/2;
            if(nums[mid]>target){
                right=mid-1;
            }else if(nums[mid]<target){
                left=mid+1;
            }else {
                return mid;
            }
        }
        return -1;
    }
    //递归
    public int binary(int[] nums, int target) {
        int l=0;
        int r= nums.length;
        return binaryChild(nums,target,l,r);
    }
    public int binaryChild(int nums[],int target,int l,int r){
        if(l>r){
            return -1;
        }
        int m=l+((r-l)>>1);
        if(nums[m]==target){
            return m;
        }else if(nums[m]>target){
            return binaryChild(nums,target,l,m);
        }else{
            return binaryChild(nums,target,m,r);
        }
    }
    //查找平方根
    public int mySqrt(int x) {
        if(x==0){
            return 0;
        }
        long l=1;
        long r=x;
        while(l<=r){
            long m=l+((r-l)>>1);
            if(m*m>(long)x){
                r=m-1;
            }else if(m*m<(long)x){
                if((m+1)*(m+1)>x){
                    return (int)m;
                }
                l=m+1;
            }else{
                return (int)m;
            }
        }
        return -1;
    }
    public int mySqrt1(int x) {
        if(x==0){
            return 0;
        }
        int l=0;
        int r=x;
        int m=x/2;
        while(l<=r){
            if((long)m*m>(long)x){
                r=m-1;
            }else if((long)m*m<(long)x){
                l=m+1;
            }else{
                return m;
            }
            m=(l+r)/2;

        }
        return m;
    }
//查找位置，返回相应的位置或者应该插入的位置
    public int searchInsert(int[] nums, int target) {
        int l=0;
        int r=nums.length;
        while(r>l){
            int mid=l+((r-l)>>1);
            if(nums[mid]>target){
                r=mid;
            }else if(nums[mid]<target){
                l=mid+1;
            }else{
                return mid;
            }
        }
        return l;
    }
//完全平方数
    public boolean isPerfectSquare(int num) {
        int l=0;
        int r=num;
        while(l<=r){
            int m=l+((r-l)>>1);
            if((long)m*m<(long)num){
                l=m+1;
            }else if((long)m*m>(long)num){
                r=m-1;
            }else{
                return true;
            }
        }
        return false;
    }
}

public class Test {
}
